BOJ_4179_불!

너비 우선 탐색(BFS)를 사용해서 불과 지훈이를 이동시키는 문제

처음에는 시간 당 불의 위치를 maze에 모두 표시하는 bfs를 돈 후, 지훈이의 이동을 bfs로 처리했다
하지만 이렇게 하니까 시간 제한이 1초라 계속 시간초과가 났다

내 생각에는 O(1000 x 1000)을 2번 하는 로직이기 때문에 1초 제한을 통과할 것 같았는데, 어떻게 수정해도 시간초과가 나서 답을 봤다

다른 사람들은 불을 담는 큐 / 지훈이 이동 큐를 따로 만든 후 각각 한 턴씩 비교하며 지훈이를 이동시켰다

이런 방식이 불의 이동을 끝까지 채울 필요가 없기 때문에 더 효율적이다

from collections import deque  
import sys  
  
input = sys.stdin.readline  
dx = [-1, 1, 0, 0]  
dy = [0, 0, 1, -1]  
  
R, C = map(int, input().split())  
maze = []  
j_pos = None  
fire_queue = deque()  
  
# 입력 및 초기화  
for i in range(R):  
    row = list(input().strip())  
    for j in range(C):  
        if row[j] == 'J':  
            j_pos = (i, j)  
            row[j] = '.'  
        elif row[j] == 'F':  
            fire_queue.append((i, j))  
    maze.append(row)  
  
  
def bfs():  
    queue = deque([(j_pos[0], j_pos[1], 0)])  
    visited = [[False] * C for _ in range(R)]  
    visited[j_pos[0]][j_pos[1]] = True  
  
    while queue:  
        # 불 먼저 이동  
        fire_size = len(fire_queue)  
        for _ in range(fire_size):  
            fx, fy = fire_queue.popleft()  
            for i in range(4):  
                nfx, nfy = fx + dx[i], fy + dy[i]  
                if 0 <= nfx < R and 0 <= nfy < C and maze[nfx][nfy] == '.':  
                    maze[nfx][nfy] = 'F'  
                    fire_queue.append((nfx, nfy))  
  
        # 지훈이 이동  
        size = len(queue)  
        for _ in range(size):  
            x, y, time = queue.popleft()  
  
            if x == 0 or x == R - 1 or y == 0 or y == C - 1:  
                return time + 1  
  
            for i in range(4):  
                nx, ny = x + dx[i], y + dy[i]  
                if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny] and maze[nx][ny] == '.':  
                    visited[nx][ny] = True  
                    queue.append((nx, ny, time + 1))  
  
    return "IMPOSSIBLE"  
  
  
print(bfs())